This invention relates generally to the field of computeraided design and graphics. It relates specifically to a drawing processor system using a set of multiple processors processing in parallel, each processor handling a group of designated display screen scanlines.
The co-pending, co-assigned applications entitled "Sequential Access Memory System," U.S. Ser. No. 078,872, filed on July 28, 1987, in the name of Ross G. Werner and Eric L. Ryherd and "Memory Address System," U.S. Ser. No. 078,873, filed on July 28, 1987, in the name of John G. Torborg and Fred K. Oliver disclose systems for storing, addressing and accessing pixel data for the pixels of a raster or other display which are suitable for use with the disclosed invention. These two applications are hereby incorporated herein by reference.
Recently, interactive three-dimensional graphics applications have become a significant portion of computer-aided design techniques. Using interactive graphics applications, an operator manipulates complex models of objects and other graphical representations. Providing realistic rendering and display of the models and performing complex operations upon them require a very large amount of arithmetical processing. For example, it is desirable to depict a complex object, such as an automobile; to rotate an image of the object about an axis; to depict shading of object surfaces based on a light source at any location; to cut a section of the object along any plane and display an image of that cross section; to assign arbitrary colors to portions of the object as determined by independent parameters; and to show a three-dimensional wire frame image of the object.
Further, providing real time interactive rendering requires a commensurately large amount of processing at the pixel level. Current commercially-available graphic systems use a single drawing processor architecture, which calculates and renders a single pixel at a time. The fastest of these systems can calculate and render a new pixel's value approximately every 50 nanoseconds, resulting in a peak performance of 20 million pixels per second. Implementing shading, an increasingly popular feature, significantly degrades performance. When rendering small, shaded triangles of less than 100 pixels in area, typically fewer than 5,000 triangles per second may be rendered. "Depth buffering" is the procedure by which the system omits surfaces of representations of objects that would be hidden by other objects from the viewpoint being rendered at the time. The rendering limit is even lower if depth buffering is also provided. For complex models of more than 5,000 triangles, the performance degrades to the point not suitable for interactive use.
A typical computer graphic system consists of a computer with peripherals, including disc drives, printers, plotters, etc. and a graphics terminal. A typical graphics terminal consists of a high resolution video display screen, user input devices including a keyboard and mouse, an image memory and a drawing processor. The drawing processor accepts high level graphics commands generated by the computer, in part in response to user input, and generates low level commands to control the display at the pixel to pixel level.
A dedicated Graphic Arithmetic Processor (referred to below as a "GAP") may be used to generate a first set of low level commands from the high level commands. The set of low-level commands generated by the GAP generally defines elementary geometric constructs such as vectors, triangles, rectangles, and arrays, each defined by coordinates in three-dimensional space. It is necessary to render each of these three-dimensional geometric shapes as a set of pixels on a two-dimensional cathode ray tube display. The GAP translates the definition of the elementary geometric constructs into pixel representations of selected elements of the constructs, such as vertices of triangular patches and end-points of vectors. The drawing processor generates a full pixel representation from the selected pixel element representation of the elementary geometric constructs.
Several architectures for the drawing processor and image memory controller have been proposed, which use multiple or parallel processing to achieve higher rendering speeds. See, for instance: Fuchs, H. "Distributing a Visible Surface Algorithm over Multiple Processors," Proceedings (ACM) 1977, Fuchs, H. and Poulton, J., "Pixel-Planes: A VLSI Oriented Design for a Raster Graphics Engine," VLSI Design No. 3 (1981) 20; Fuchs, H., Goldfeather, J., Hultquist, J., "Fast Constructive Solid Geometry Display in the Pixel Powers Graphics System," Computer Graphics (ACM) 20, 4 (1986), 107; Parke, F. I., "Simulations and Expected Performance Analysis of Multiprocessor Z Buffer System," Computer Graphics (ACM) 14, 3 (1980) 48; and Niimi, H., Emai, Y., Murakami, M., Tomita, S., and Hagiwara, H., "A Parallel Processor System for 3-Dimensional Color Graphics," Computer Graphics (ACM) 18, 3 (1984), 67.
An approach proposed by Fuchs (1977) and discussed by Parke (1980) provides a broadcast controller, which distributes polygonal patches to multiple image processors. According to this approach, each image processor renders only those pixels determined by a preset interlace pattern. For example, a two-processor system may be configured with an interlace pattern dependent upon scanline position, so that a first processor renders all pixels on even scanlines and the second processor renders pixels on odd scanlines. According to the proposed model, each processor receives all of the information for every polygon, but only renders those pixels assigned to it by the interlace pattern. Both processors redundantly perform polygon scan conversion and differential calculations, thereby incurring unnecessary overhead and consequently reducing performance.
Smart memory approaches have also been proposed whereby the screen is divided up into blocks of pixels (e.g. an 8.times.8 block) and a memory chip is provided for each pixel location in the block (e.g. col. 4, row 6). Each such memory chip (64 in this example) has associated with it a processor. See generally Fuchs, (1986) above and Gupta, S., Sproull, R. and Sutherland, I., "A VLSI Architecture for Updating Raster-Scan Displays", Computer Graphics (ACM) 1513 (1981).
In the past, high performance drawing architectures have been designed in which the image memory update bandwidth cannot support the drawing rate. This wastes the high speed of the rendering engine.